
#ifndef tree_hh_
#define tree_hh_

#include <cassert>
#include <memory>
#include <stdexcept>
#include <iterator>
#include <set>
#include <queue>
#include <algorithm>

// HP-style construct/destroy have gone from the standard,
// so here is a copy.

namespace kp {

	template <class T1, class T2>
	void constructor(T1* p, T2& val) 
	{
		new ((void *) p) T1(val);
	}

	template <class T1>
	void constructor(T1* p) 
	{
		new ((void *) p) T1;
	}

	template <class T1>
	void destructor(T1* p)
	{
		p->~T1();
	}

}

/// A node in the tree, combining links to other nodes as well as the actual data.
template<class T>
class tree_node_ 
{ // size: 5*4=20 bytes (on 32 bit arch), can be reduced by 8.
public:
	tree_node_<T> *parent;
	tree_node_<T> *first_child, *last_child;
	tree_node_<T> *prev_sibling, *next_sibling;
	T data;
}; // __attribute__((packed));

template <class T, class tree_node_allocator = std::allocator<tree_node_<T> > >
class tree {
protected:
	typedef tree_node_<T> tree_node;
public:
	/// Value of the data stored at a node.
	typedef T value_type;

	class iterator_base;
	class pre_order_iterator;
	class sibling_iterator;

	tree()
	{
		head_initialise_();
	};
	tree(const T& x)
	{
		head_initialise_();
		set_head(x);
	};
	tree(const iterator_base& other)
	{
		head_initialise_();
		set_head((*other));
		replace(begin(), other);
	};

	tree(const tree<T, tree_node_allocator>& other)
	{
		head_initialise_();
		copy_(other);
	};
	~tree()
	{
		clear();
		alloc_.deallocate(head,1);
		alloc_.deallocate(feet,1);
	};
	void operator=(const tree<T, tree_node_allocator>& other)
	{
		copy_(other);
	};

	class iterator_base 
	{
	public:
		typedef T                               value_type;
		typedef T*                              pointer;
		typedef T&                              reference;
		typedef size_t                          size_type;
		typedef ptrdiff_t                       difference_type;
		typedef std::bidirectional_iterator_tag iterator_category;

		iterator_base(): node(0), skip_current_children_(false)
		{};
		iterator_base(tree_node * tn): node(tn), skip_current_children_(false)
		{};

		T&	operator*() const
		{
			return node->data;
		};
		T*	operator->() const
		{
			return &(node->data);
		};

		/// When called, the next increment/decrement skips children of this node.
		void         skip_children()
		{
			skip_current_children_=true;
		};
		void         skip_children(bool skip)
		{
			skip_current_children_=skip;
		};
		/// Number of children of the node pointed to by the iterator.
		unsigned int number_of_children() const
		{
			tree_node *pos=node->first_child;
			if(pos==0) return 0;

			unsigned int ret=1;
			while(pos!=node->last_child) {
				++ret;
				pos=pos->next_sibling;
			}
			return ret;
		};

		sibling_iterator begin() const
		{
			if(node->first_child==0) 
				return end();

			sibling_iterator ret(node->first_child);
			ret.parent_=this->node;
			return ret;
		};
		sibling_iterator end() const
		{
			sibling_iterator ret(0);
			ret.parent_=node;
			return ret;
		};

		tree_node *node;
	protected:
		bool skip_current_children_;
	};

	/// Depth-first iterator, first accessing the node, then its children.
	class pre_order_iterator : public iterator_base { 
	public:
		pre_order_iterator(): iterator_base(0)
		{
		};
		pre_order_iterator(tree_node *tn)
			: iterator_base(tn)
		{
		};
		pre_order_iterator(const iterator_base& other)
			: iterator_base(other.node)
		{
		};
		pre_order_iterator(const sibling_iterator& other)
			: iterator_base(other.node)
		{
			if(this->node==0) {
				if(other.range_last()!=0)
					this->node=other.range_last();
				else 
					this->node=other.parent_;
				this->skip_children();
				++(*this);
			}
		};

		bool    operator==(const pre_order_iterator& other) const
		{
			if(other.node==this->node) return true;
			else return false;
		};
		bool    operator!=(const pre_order_iterator& other) const
		{
				if(other.node!=this->node) return true;
				else return false;
		};
		pre_order_iterator&  operator++()
		{
			assert(this->node!=0);
			if(!this->skip_current_children_ && this->node->first_child != 0) {
				this->node=this->node->first_child;
			}
			else {
				this->skip_current_children_=false;
				while(this->node->next_sibling==0) {
					this->node=this->node->parent;
					if(this->node==0)
						return *this;
				}
				this->node=this->node->next_sibling;
			}
			return *this;
		};
		pre_order_iterator&  operator--()
		{
			assert(this->node!=0);
			if(this->node->prev_sibling) {
				this->node=this->node->prev_sibling;
				while(this->node->last_child)
					this->node=this->node->last_child;
			}
			else {
				this->node=this->node->parent;
				if(this->node==0)
					return *this;
			}
			return *this;
		};
		pre_order_iterator   operator++(int)
		{
			pre_order_iterator copy = *this;
			++(*this);
			return copy;
		};
		pre_order_iterator   operator--(int)
		{
			pre_order_iterator copy = *this;
			--(*this);
			return copy;
		};
		pre_order_iterator&  operator+=(unsigned int)
		{
			while(num>0) {
				++(*this);
				--num;
			}
			return (*this);
		};
		pre_order_iterator&  operator-=(unsigned int)
		{
			while(num>0) {
				--(*this);
				--num;
			}
			return (*this);
		};
	};

	/// The default iterator types throughout the tree class.
	typedef pre_order_iterator            iterator;

	/// Iterator which traverses only the nodes which are siblings of each other.
	class sibling_iterator : public iterator_base {
	public:
		sibling_iterator(): iterator_base()
		{
			set_parent_();
		};
		sibling_iterator(tree_node *other): iterator_base(other)
		{
			set_parent_();
		};
		sibling_iterator(const sibling_iterator& other): iterator_base(other), parent_(other.parent_)
		{
		};
			
		sibling_iterator(const iterator_base& tn): iterator_base(tn)
		{
			set_parent_();
		};

		bool    operator==(const sibling_iterator& other) const
		{
			if(other.node==this->node) return true;
			else return false;
		};
		bool    operator!=(const sibling_iterator& other) const
		{
			if(other.node!=this->node) return true;
			else return false;
		};
		sibling_iterator&  operator++()
		{
			if(this->node)
				this->node=this->node->next_sibling;
			return *this;
		};
		sibling_iterator&  operator--()
		{
			if(this->node) this->node=this->node->prev_sibling;
			else {
				assert(parent_);
				this->node=parent_->last_child;
			}
			return *this;
		};
		sibling_iterator   operator++(int)
		{
			sibling_iterator copy = *this;
			++(*this);
			return copy;
		};
		sibling_iterator   operator--(int)
		{
			sibling_iterator copy = *this;
			--(*this);
			return copy;
		};
		sibling_iterator&  operator+=(unsigned int)
		{
			while(num>0) {
				++(*this);
				--num;
			}
			return (*this);
		};
		sibling_iterator&  operator-=(unsigned int)
		{
			while(num>0) {
				--(*this);
				--num;
			}
			return (*this);
		};

		tree_node *range_first() const
		{
			tree_node *tmp=parent_->first_child;
			return tmp;
		};
		tree_node *range_last() const
		{
			return parent_->last_child;
		};

		tree_node *parent_;
	private:
		void set_parent_()
		{
			parent_=0;
			if(this->node==0) return;
			if(this->node->parent!=0)
				parent_=this->node->parent;
		};
	};

	bool is_valid(const iterator_base& it) const
	{
		if(it.node==0 || it.node==feet || it.node==head) return false;
		else return true;
	}

	/// Return iterator to the beginning of the tree.
	inline pre_order_iterator   begin() const
	{
		return pre_order_iterator(head->next_sibling);
	};
	/// Return iterator to the end of the tree.
	inline pre_order_iterator   end() const
	{
		return pre_order_iterator(feet);
	};

	sibling_iterator     begin(const iterator_base& pos) const
	{
		assert(pos.node!=0);
		if(pos.node->first_child==0) {
			return end(pos);
		}
		return pos.node->first_child;
	};
	/// Return sibling end iterator for children of given node.
	sibling_iterator     end(const iterator_base& pos) const
	{
		sibling_iterator ret(0);
		ret.parent_=pos.node;
		return ret;
	};
	/// Return leaf iterator to the first leaf of the tree.

	/// Return iterator to the parent of a node.
	template<typename	iter> 
	static iter parent(iter position) 
	{
		assert(position.node!=0);
		return iter(position.node->parent);
	};
	/// Return iterator to the previous sibling of a node.
	template<typename iter> 
	iter previous_sibling(iter position) const
	{
		assert(position.node!=0);
		iter ret(position);
		ret.node=position.node->prev_sibling;
		return ret;
	};
	/// Return iterator to the next sibling of a node.
	template<typename iter> 
	iter next_sibling(iter position) const
	{
		assert(position.node!=0);
		iter ret(position);
		ret.node=position.node->next_sibling;
		return ret;
	};
	/// Erase all nodes of the tree.
	void     clear()
	{
		if(head)
			while(head->next_sibling!=feet)
				erase(pre_order_iterator(head->next_sibling));
	};
	template<class iter> iter erase(iter it)
	{
		tree_node *cur=it.node;
		assert(cur!=head);
		iter ret=it;
		ret.skip_children();
		++ret;
		erase_children(it);
		if(cur->prev_sibling==0) {
			cur->parent->first_child=cur->next_sibling;
		}
		else {
			cur->prev_sibling->next_sibling=cur->next_sibling;
		}
		if(cur->next_sibling==0) {
			cur->parent->last_child=cur->prev_sibling;
		}
		else {
			cur->next_sibling->prev_sibling=cur->prev_sibling;
		}

		kp::destructor(&cur->data);
		alloc_.deallocate(cur,1);
		return ret;
	};
	
	void erase_children(const iterator_base& it)
	{
		//	std::cout << "erase_children " << it.node << std::endl;
		if(it.node==0) return;

		tree_node *cur=it.node->first_child;
		tree_node *prev=0;

		while(cur!=0) {
			prev=cur;
			cur=cur->next_sibling;
			erase_children(pre_order_iterator(prev));
			kp::destructor(&prev->data);
			alloc_.deallocate(prev,1);
		}
		it.node->first_child=0;
		it.node->last_child=0;
		//	std::cout << "exit" << std::endl;
	};
	/// Insert empty node as last/first child of node pointed to by position.
	template<typename iter> iter append_child(iter  position)
	{
		assert(position.node!=head);
		assert(position.node);

		tree_node *tmp=alloc_.allocate(1,0);
		kp::constructor(&tmp->data);
		tmp->first_child=0;
		tmp->last_child=0;

		tmp->parent=position.node;
		if(position.node->last_child!=0) 
		{
			position.node->last_child->next_sibling=tmp;
		}
		else 
		{
			position.node->first_child=tmp;
		}
		tmp->prev_sibling=position.node->last_child;
		position.node->last_child=tmp;
		tmp->next_sibling=0;
		return tmp;
	}; 

	/// Insert node as last/first child of node pointed to by position.
	template<typename iter> iter append_child(iter position, const T& x)
	{
		// If your program fails here you probably used 'append_child' to add the top
		// node to an empty tree. From version 1.45 the top element should be added
		// using 'insert'. See the documentation for further information, and sorry about
		// the API change.
		assert(position.node!=head);
		assert(position.node);

		tree_node* tmp = alloc_.allocate(1,0);
		kp::constructor(&tmp->data, x);
		tmp->first_child=0;
		tmp->last_child=0;

		tmp->parent=position.node;
		if(position.node->last_child!=0) 
		{
			position.node->last_child->next_sibling=tmp;
		}
		else 
		{
			position.node->first_child=tmp;
		}
		tmp->prev_sibling=position.node->last_child;
		position.node->last_child=tmp;
		tmp->next_sibling=0;
		return tmp;
	};
	/// Append the node (plus its children) at other_position as last/first child of position.
	template<typename iter> iter append_child(iter position, iter other_position)
	{
		assert(position.node!=head);
		assert(position.node);

		sibling_iterator aargh=append_child(position, value_type());
		return replace(aargh, other);
	};
	
	/// Insert node as previous sibling of node pointed to by position.
	template<typename iter> iter insert(iter position, const T& x)
	{
		if(position.node==0) 
		{
			position.node=feet; // Backward compatibility: when calling insert on a null node,
			// insert before the feet.
		}
		tree_node* tmp = alloc_.allocate(1,0);
		kp::constructor(&tmp->data, x);
		tmp->first_child=0;
		tmp->last_child=0;

		tmp->parent=position.node->parent;
		tmp->next_sibling=position.node;
		tmp->prev_sibling=position.node->prev_sibling;
		position.node->prev_sibling=tmp;

		if(tmp->prev_sibling==0) 
		{
			if(tmp->parent) // when inserting nodes at the head, there is no parent
				tmp->parent->first_child=tmp;
		}
		else
			tmp->prev_sibling->next_sibling=tmp;
		return tmp;
	};
	/// Specialisation of previous member.
	sibling_iterator insert(sibling_iterator position, const T& x)
	{
		tree_node* tmp = alloc_.allocate(1,0);
		kp::constructor(&tmp->data, x);
		tmp->first_child=0;
		tmp->last_child=0;

		tmp->next_sibling=position.node;
		if(position.node==0) { // iterator points to end of a subtree
			tmp->parent=position.parent_;
			tmp->prev_sibling=position.range_last();
			tmp->parent->last_child=tmp;
		}
		else 
		{
			tmp->parent=position.node->parent;
			tmp->prev_sibling=position.node->prev_sibling;
			position.node->prev_sibling=tmp;
		}

		if(tmp->prev_sibling==0) 
		{
			if(tmp->parent) // when inserting nodes at the head, there is no parent
				tmp->parent->first_child=tmp;
		}
		else
			tmp->prev_sibling->next_sibling=tmp;
		return tmp;
	};


	/// Count the total number of nodes.
	size_t   size() const
	{
		size_t i=0;
		pre_order_iterator it=begin(), eit=end();
		while(it!=eit) 
		{
			++i;
			++it;
		}
		return i;
	};
	/// Count the total number of nodes below the indicated node (plus one).
	size_t   size(const iterator_base& top) const	
	{
		size_t i=0;
		pre_order_iterator it=top, eit=top;
		eit.skip_children();
		++eit;
		while(it!=eit) 
		{
			++i;
			++it;
		}
		return i;
	};
	/// Check if tree is empty.
	bool     empty() const
	{
		pre_order_iterator it=begin(), eit=end();
		return (it==eit);
	};
	/// Compute the depth to the root or to a fixed other iterator.
	static int depth(const iterator_base& it) 
	{
		tree_node* pos=it.node;
		assert(pos!=0);
		int ret=0;
		while(pos->parent!=0) 
		{
			pos=pos->parent;
			++ret;
		}
		return ret;
	};
	static int depth(const iterator_base& it, const iterator_base& root) 
	{
		tree_node* pos=it.node;
		assert(pos!=0);
		int ret=0;
		while(pos->parent!=0 && pos!=root.node) 
		{
			pos=pos->parent;
			++ret;
		}
		return ret;
	};
	/// Determine the index of a node in the range of siblings to which it belongs.
	unsigned int index(sibling_iterator it) const
	{
		unsigned int ind=0;
		if(it.node->parent==0) 
		{
			while(it.node->prev_sibling!=head) 
			{
				it.node=it.node->prev_sibling;
				++ind;
			}
		}
		else 
		{
			while(it.node->prev_sibling!=0) 
			{
				it.node=it.node->prev_sibling;
				++ind;
			}
		}
		return ind;
	};
	/// Inverse of 'index': return the n-th child of the node at position.
	static sibling_iterator child(const iterator_base& position, unsigned int)
	{
		tree_node *tmp=it.node->first_child;
		while(num--) 
		{
			assert(tmp!=0);
			tmp=tmp->next_sibling;
		}
		return tmp;
	};
	/// Return iterator to the sibling indicated by index
	sibling_iterator sibling(const iterator_base& position, unsigned int)
	{
		tree_node *tmp;
		if(it.node->parent==0) 
		{
			tmp=head->next_sibling;
			while(num) 
			{
				tmp = tmp->next_sibling;
				--num;
			}
		}
		else 
		{
			tmp=it.node->parent->first_child;
			while(num) 
			{
				assert(tmp!=0);
				tmp = tmp->next_sibling;
				--num;
			}
		}
		return tmp;
	};  				

	/// Comparator class for iterators (compares pointer values; why doesn't this work automatically?)
	class iterator_base_less {
	public:
		bool operator()(const typename tree<T, tree_node_allocator>::iterator_base& one,
			const typename tree<T, tree_node_allocator>::iterator_base& two) const
		{
			return one.node < two.node;
		}
	};
	tree_node *head, *feet;    // head/feet are always dummy; if an iterator points to them it is invalid
private:
	tree_node_allocator alloc_;
	void head_initialise_()
	{ 
		head = alloc_.allocate(1,0); // MSVC does not have default second argument 
		feet = alloc_.allocate(1,0);

		head->parent=0;
		head->first_child=0;
		head->last_child=0;
		head->prev_sibling=0; //head;
		head->next_sibling=feet; //head;

		feet->parent=0;
		feet->first_child=0;
		feet->last_child=0;
		feet->prev_sibling=head;
		feet->next_sibling=0;
	};
	void copy_(const tree<T, tree_node_allocator>&  other) 
	{
		clear();
		pre_order_iterator it=other.begin(), to=begin();
		while(it!=other.end()) {
			to=insert(to, (*it));
			it.skip_children();
			++it;
		}
		to=begin();
		it=other.begin();
		while(it!=other.end()) {
			to=replace(to, it);
			to.skip_children();
			it.skip_children();
			++to;
			++it;
		}
	};

	/// Comparator class for two nodes of a tree (used for sorting and searching).
};

#endif